FIG. 1 shows a conventional a hierarchically organized communications network 10. In particular, the communications network has a wide area network (WAN), such as the internet, at the highest level of the hierarchy. A campus network 15 is interconnected to the WAN by a router r1. The campus network 15 is so called because it is typically located at a single geographic campus of several buildings. The interconnections may include any combination of wires, coaxial cables, optical fibers, circuit switches, packet switches, etc. The router r1, interconnects a backbone network of the campus network 15 to the WAN. Connected to the backbone network are additional routers r2, r3 and r4. Each additional router r2, r3 and r4 connects a respective subnetwork A, B or C to the backbone network. The campus network 15 is at a middle level of the hierarchy and subnetworks A,B & C of the campus network 15 are at a lower level in the hierarchy. The subnetworks A,B,C are typically isolated to a single, small geographic area such as an office building or floor of an office building. The WAN, on the other hand, typically sprawls from geographic area to geographic area. The WAN itself typically includes a number of routers (not shown) for routing communications from campus network to campus network.
The communication between routers on the WAN and on the backbone network is illustratively achieved according to the internet protocol (IP). (Herein, protocol means a collection of semantic and syntactic rules obeyed by the devices which communicate according to the protocol.)
The router r2 is connected to bridges b1 and b2 of the subnetwork A, the router r3 is connected to bridge b3 of the subnetwork B and the router r4 is connected to the bridge b4 of the subnetwork C. Each bridge b1-b4 is connected to one or more network segments or collision domains which illustratively are local area networks (LANs). The bridge b1 is connected to network segments L1 and L2, the bridge b2 is connected to network segments L2, L3 and L4, the bridge b3 is connected to network segments L5, L6 and L7 and the bridge b4 is connected to network segment L8. Each network segment L1-L8 comprises one or more interconnected hosts computers h1-h17. The network segment L1 includes hosts h1, h2 and h3, the network segment L2 includes the host h4, the network segment L3 includes the hosts h5, h6 and h7, the network segment L4 includes the host h8, the network segment L5 includes the host h9, the network segment L6 includes the hosts 10 and h11, the network segment L7 includes the hosts h12, h13 and h14 and the network segment L8 includes the hosts h15, h16 and h17. The network segments L1-L8 may be Ethernet LANs, token ring LANs or FDDI LANs, for example.
Communication may be achieved locally within each network segment L1-L8 according to one of a number of protocols. Since most deployed network segments L1-L8 are Ethernet LANs, the Ethernet protocol for communication is used to illustrate the invention. According to the Ethernet protocol, each host computer is connected via an I/O interface to a common broadcast medium (which broadcast medium may be carried by a coaxial cable, unshielded twisted pairs of wires, etc.). A host communicates on the medium by transmitting a bitstream organized into packets. FIG 2 illustrates an illustrative packet 20, which comprises a header section 22 and a payload section 24. A host which desires to communicate writes data in the payload section 24, and an address of the intended recipient host in the header section 22. (Illustratively, all hosts on a network segment are assigned a unique identifier or address.) If the common broadcast medium is not currently being used, then the host transmits its packet 20 from an I/O interface connected to the host onto the common broadcast medium. If the common broadcast medium is currently being used by another host to transmit a packet, then the host waits until the common broadcast medium is available. The transmitted packet 20 is received at the I/O interface of each other host on the network segment. Each host then examines the destination address written in the header section 22 of the packet 20. If the destination address matches the destination address of the host, the host accepts the packet 20 and may examine the contents of the payload section 24. If the destination address does not match, the host discards the packet 20.
It is possible that two hosts of the same network segment may attempt to transmit a packet concurrently. If this happens, a collision is said to occur. According to the Carrier Sense Multiple Access with Collision Detection (CSMA/CD) protocol, in the event of a collision, each host transmits a jamming signal for a specified period of time and waits a variable amount of time before reattempting transmission of its packet. See U.S. Pat. No. 5,355,375. Collisions are only possible within an individual collision domain or network segment. For instance, the communication amongst the hosts h1-h3 and bridge b1 in the network segment L1 does not effect the communication amongst the host h4 and bridge b1 in the network segment L2. The delay incurred in transmitting a packet on a network segment (as caused by collisions or otherwise) increases with the increase of communications traffic on each segment.
Sometimes it is desirable to communicate from a host in one network segment to a host in another network segment of the same subnetwork. Such communication may be achieved using the bridges b1-b4. The bridge enables inter-segment communication while isolating the two network segments so that they operate as independent collision domains. The bridges b1-b4 also can enable communication between network segments that communicate according to different protocols. For instance, the bridge b1 can enable communication by the host h4 in the network segment L2, which is a Token Ring LAN, with the host h2 in the network segment L1, which is an Ethernet LAN.
The bridges within a subnetwork (e.g., the bridges b1-b2 in the subnetwork A) pass control packets between each other to determine the best route for reaching each host in each attached network segment. Thereafter, each bridge receives each packet transmitted on its attached network segments. If the bridge (e.g., bridge b1) receives a packet from one network segment (e.g., L1) containing a destination address of a host in another network segment, (e.g., the host h8 in network segment L4) the bridge transmits the packet in another attached network segment on a route to the network segment that contains the destination host. For instance, the route from host h 1 in network segment L1 to the host h8 in the network segment L4 illustratively comprises: h1.fwdarw.L1.fwdarw.b1.fwdarw.L2.fwdarw.b2.fwdarw.L4.fwdarw.h8. Thus, the bridge b1 retransmits a packet received from host h 1 destined to host h8 on network segment L2.
In addition to enabling inter-segment communication within a subnetwork, the bridges enable the hosts in one subnetwork to communicate with the hosts in other subnetworks. To that end, IP (internet protocol) addresses may be assigned to each host which includes the destination host's address in the particular subnetwork concatenated to at least a unique address that is assigned to the subnetwork in which the destination host is located. As an example, suppose the host h1 in the subnetwork A wishes to transmit a packet to the host h15 in the subnetwork C. The host h1 writes the IP address of the node h15 (which includes at least the destination address of the subnetwork C concatenated to the destination address of the host h15) in a packet and transmits the packet on its network segment L1. The packet is received at, amongst other places, the bridge b1. If a bridge (e.g., the bridge b1) in a particular subnetwork receives a packet with a destination address that is foreign to the particular subnetwork, the bridge transmits the packet to its attached router (e.g., r2). The packet is then transmitted via the backbone network to the router that connects to the subnetwork containing the destination host. For instance, the packet may be transmitted from the router r2 via the backbone network to the router r4. To that end, each router which receives a packet illustratively uses the destination address (or a portion thereof) to index a routing table stored at the router. The indexed router table entry indicates the next router to which the packet must be transmitted. When the packet reaches the router (e.g., router r4) that attaches the subnetwork (e.g., subnetwork C) containing the destination host (e.g., host h15), the router transfers the packet to the attached bridge (e.g., b4). The bridge then transmits the packet to the destination host.
The discussion above has been limited to unicast packet communication wherein a packet is transmitted from a single source host to a single destination host. The network 10 also supports multicast communication, wherein a packet is transmitted from a single source host to multiple hosts. U.S. Pat. No. 5,331,637 describes multicast routing and, in particular, how to implement multicast routing at the WAN level of the hierarchy. Illustratively, multicast communication of packets is supported in the communications network 10 at the network level of communications according to the Internet Group Management Protocol (IGMP), IETF RFC 112, Host Extensions for IP Multicasting. According to this protocol, multicast groups of hosts are identified, wherein each group is a collection of destination hosts for packets for a particular communication. Each multicast group is assigned a special multicast address which bears no relation to any single host of the multicast group.
Each router which connects a campus network 15 to the WAN (e.g., the router r1) periodically transmits a "Host Membership Query" multicast control packet with a destination address that specifies all of the hosts of the campus network 15. In response, each host transmits back to the router (e.g., the router r1) a "Host Membership Report" multicast control packet that indicates all of the groups to which the host belongs. Furthermore, a host can transmit a "Join Host Group" or "Leave Host Group" multicast control packet to the router (e.g., the router r1) at any time to join or leave a multicast group. The router receives these messages and updates its routing tables accordingly.
When a host, e.g., the host h 1, desires to transmit a multicast packet, it writes a multicast address of an appropriate multicast group in the destination field. The host then transmits the packet to its attached bridge, e.g., the bridge b1 (via the subnetwork L1). The bridge has no way of knowing the location of the destination host (because the multicast destination address bears no relationship to the destination address of a single host). Thus, the bridge retransmits the multicast packet to each attached subnetwork and router, other than the subnetwork or router from which the packet originated, e.g., the subnetworks L2, L3 and the router r2. The attached router, e.g., the router r2, accesses its routing table using the multicast destination address. However, unlike before, the accessed routing table entry may indicate more than one next router to which the packet must be transmitted, e.g., the router r1 and the router r3. The router transmits a copy of the packet to each indicated next router. Thus, the packet is selectively routed and replicated in route. Each router that receives a copy of the multicast packet performs the same table access procedure. Eventually, a router, e.g., the router r4, receives a packet that must be transmitted to an attached subnetwork, e.g., the subnetwork C.
When a multicast packet is received at a bridge of the subnetwork, e.g., the bridge b4 of the subnetwork C, the bridge has no way of knowing to which attached network segment (or router) the packet is destined. This is because the packet has a multicast address which bears no relationship to any individual host. Furthermore, the multicast packet can be destined to more than one host in more than one attached network segment and or router. Thus, the bridge retransmits the multicast packet in each attached network segment and to each attached router. The packets transmitted in the network segments are received by each host. Each host then compares the multicast destination address to the multicast destination addresses of the groups of which it is a member. If the host is a member of the same group as indicated in the packet, the host receives the packet. Otherwise, the host discards the packet.
The problem with the above-noted multicast communication scheme is that it wastes bandwidth in the subnetworks. In particular, a bridge retransmits a received multicast packet in each attached network segment even if one of the attached network segments is devoid of destination hosts of the multicast packet (i.e., even if the network segment does not have any hosts that are members of the multicast group of the multicast packet). This results in unnecessary bandwidth reduction in some attached network segments that are devoid of destination hosts. Considering that much multicast traffic in the future is intended to be bandwidth intensive multimedia traffic, i.e., video and/or audio, the wasted bandwidth can be very high and can noticeably degrade performance on a network segment. In the past, the solution to improving network segment performance is to reconfigure the campus network by increasing the number of routers and redistributing (i.e., reconnecting) the network segments or hosts amongst the routers. However, this solution is disadvantageous because routers are relatively expensive and difficult to manage.
S. Deering, Multicast Routing in Internetworks and Extended LANs, ACM SYMPOSIUM ON COMMUNICATION ARCHITECTURES AND PROTOCOLS, ACM SIGCOMM pp.55-64, Aug. 1988 proposes an alternative solution. According to the Deering reference, bridges only retransmit multicast packets over "links" on routes to destination host of the multicast packets (wherein a "link" is a communication connection). To that end, each bridge constructs a multicast forwarding table which is maintained at the bridge. The bridge accesses the multicast forwarding table using the multicast group as an address to determine onto which links a received multicast packet must be retransmitted. The Deering reference teaches that the hosts transmit special control packets that are destined to all bridges of the campus network indicating to which multicast group the host belongs. The bridges compile such information, in order to construct the multicast forwarding table and to determine when entries of the multicast forwarding table have become stale and therefore must be discarded.
There are two problems with the proposed Deering solution. First, extra control packets must be transmitted between the hosts and the bridges in order to construct the multicast forwarding tables. This increases traffic on the network segments. Second, and more importantly, all hosts are specially adapted in accordance with the Deering scheme so that they periodically transmit the special multicast control packets in order to maintain their memberships. The solution is therefore not entirely "plug-and-play" from the perspective of the hosts.
It is therefore an object of the present invention to overcome the disadvantages of the prior art. It is a particular object of the present invention to prevent multicast communication traffic that originates from, or is destined to, outside of a subnetwork from degrading the communication performance within the subnetwork.